# -*- coding: latin-1 -*-
# Copyright (c) 2007-2009 Jorge Ortiz Romo <jortizromo@gmail.com>
#                         Freymam Vallejo Cuero <freturn@gmail.com>
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:

# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.

# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
# Import the module and instantiate a pygraph object

'''
Created on Dec 7, 2009

@author: Freymam Vallejo
@author: Jorge Ortiz
'''

from functools import reduce

def digraph_find_all_cycles_for_node(graph, start, end, iteration, path=[]):
    """
    Find all cycles from start to same node

    @type graph: graph, digraph.
    @param graph: graph, digraph.

    @type start: node
    @param start: initial node on the path

    @type end: node
    @param end: finish node on the path

    @type path: list
    @param path: 

    @rtype: list.
    @return: list with all cycles from start to same node.
    """

    
    path = path + [start]

    if start == end and iteration > 1:
        return [path]
    if not graph.has_node(start):
        return []
    paths = []
    
    for node in graph.neighbors(start):
        if node not in path or node == path[0]:
            newpaths = digraph_find_all_cycles_for_node(graph, node, end, iteration + 1, path)
            for newpath in newpaths:
                paths.append(newpath)
        
    return paths

def digraph_find_all_semicycles_for_node(graph, start, end, iteration, path=[]):
    """
    Find all cycles from start to same node

    @type graph: graph, digraph.
    @param graph: graph, digraph.

    @type start: node
    @param start: initial node on the path

    @type end: node
    @param end: finish node on the path

    @type path: list
    @param path: used in internal computes

    @rtype: list.
    @return: list with all cycles from start to same node.
    """

    
    path = path + [start]

    if start == end and iteration > 1:
        return [path]
    if not graph.has_node(start):
        return []
    paths = []

    nodes = graph.neighbors(start)
    if iteration > 1:
        nodes = nodes + graph.incidents(start)
    for node in nodes:
        if node not in path or node == path[0]:
            if iteration == 2 and node == path[0] and node not in graph.neighbors(start):
                break
            newpaths = digraph_find_all_semicycles_for_node(graph, node, end, iteration + 1, path)
            for newpath in newpaths:
                paths.append(newpath)
        
    return paths

def digraph_is_Equal_cycle(cycle1, cycle2):
    """
    Find if two cycles are equal.

    @type cycle1: list.
    @param cycle1: list of nodes.

    @type cycle2: list.
    @param cycle2: list of nodes.

    @rtype: bool.
    @return: it is True if cycles are equals.
    """
    cycle_len = cycle1.__len__()
    if cycle_len != cycle2.__len__() or cycle_len < 3:
        return False

    cycle1.pop(0)
    cycle2.pop(0)

    i = 0
    while cycle1[0] != cycle2[0] and i < cycle_len:
        cycle2.append(cycle2.pop(0))
        i +=  1
    if cycle1[0] != cycle2[0]:
        cycle1 = cycle1.append(cycle1[0])
        cycle2 = cycle2.append(cycle2[0])
        return False

    equal = cycle1 == cycle2
    cycle1 = cycle1.append(cycle1[0])
    cycle2 = cycle2.append(cycle2[0])

    return equal
        

def digraph_find_all_cycles(graph):
    """
    Find all cycles from start to same node

    @type graph: graph, digraph.
    @param graph: graph, DiGraph.

    @rtype: list.
    @return: list with all cycles from start to same node.
    """

    cycles = []
    for node in graph:
        cycles_nodal = digraph_find_all_cycles_for_node(graph, node, node, 1)
        for cycle in cycles_nodal:
            cycles.append(cycle)

    for i in range(len(cycles)):
        for j in range(i, len(cycles)):
            if i!=j and digraph_is_Equal_cycle(cycles[i], cycles[j]):
                cycles[j] = []

    cycles = list( filter(lambda x: x!=[], cycles) )

    return cycles

def digraph_find_all_semicycles(graph):
    """
    Find all cycles from start to same node

    @type graph: graph, digraph.
    @param graph: graph, DiGraph.

    @rtype: list.
    @return: list with all cycles from start to same node.
    """

    cycles = []
    for node in graph:
        cycles_nodal = digraph_find_all_semicycles_for_node(graph, node, node, 1)
        for cycle in cycles_nodal:
            cycles.append(cycle)

    for i in range(len(cycles)):
        for j in range(i, len(cycles)):
            if i!=j and digraph_is_Equal_cycle(cycles[i], cycles[j]):
                cycles[j] = []

    cycles = list( filter(lambda x: x!=[], cycles) )

    return cycles


def digraph_find_all_signed_cycles(digraph):
    """
    Find all cycles from start to same node including the relationship weights.

    @type graph: graph, digraph.
    @param graph: graph, DiGraph.

    @rtype: list.
    @return: list with all cycles from start to same node.
    """
    
    cycles = digraph_find_all_semicycles(digraph)
    
    weighted_cycles = []
    for cycle in cycles:
        weights = []
        for i in range( len( cycle) -1):
            if digraph.has_edge (cycle[i], cycle[i+1]):
                weights.append( digraph.edge_weight (cycle[i], cycle[i+1]))
            elif digraph.has_edge (cycle[i+1], cycle[i]):
                weights.append( digraph.edge_weight (cycle[i+1], cycle[i]))
        weighted_cycles.append( ( cycle, reduce( lambda x, y: x*y, weights)) )

    return weighted_cycles
